package com.zyk.leetcode;

import java.util.HashMap;

/**
 * @author zhangsan
 * @date 2021/4/4 21:20
 */
public class J35 {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + (next==null? "null": next.val) +
                    ", random=" + (random == null?"null":random.val) +
                    '}';
        }
    }
    public static Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            Node target = map.get(cur);
            target.next = map.get(cur.next);
            target.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    // 形成一条大链
    public static Node copyRandomList2(Node head) {
        if(head == null) {
            return head;
        }
        Node cur  = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        // 设置复制的元素的random
        cur = head;
        while (cur != null) {
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 分割
        cur = head;
        Node r = cur.next;
        while (cur != null) {
            Node target = cur.next;

            Node next = cur.next.next;
            Node targetNext = target.next==null? null : target.next.next;

            cur.next = next;
            target.next = targetNext;

            cur = next;
        }
        return r;
    }


    // for test
    public static void print(Node head) {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        // head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node head = new Node(7);
        head.next = new Node(13);
        head.next.next = new Node(11);
        head.next.next.next = new Node(10);
        head.next.next.next.next = new Node(1);

        head.next.random = head;
        head.next.next.random = head.next.next.next.next;
        head.next.next.next.random = head.next.next;
        head.next.next.next.next.random = head;

        print(head);

        head = copyRandomList(head);

        print(head);

        head = copyRandomList2(head);

        print(head);


    }

}
